#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

template <typename Iterator>
void __median_of_3(Iterator a,Iterator b,Iterator c){
	if (*a < *b)
		std::swap(*a,*b);
	if (*c < *b)
		std::swap(*c,*b);
	if (*a > *c)
		std::swap(*a,*c);
}

template <typename Iterator>
Iterator __partition(Iterator first,Iterator last){
	typedef typename std::iterator_traits<Iterator>::value_type value_t;
	__median_of_3(first,first + (last - first) / 2,last-1);
	value_t pivot = *first;
	Iterator follow = first;
	Iterator next = first;
	++next;
	for (; next < last; ++next){
		if (*next <= pivot){
			++follow;
			if (next != follow)
				swap(*next,*follow);
		}
	}
	//if (*follow != *first && follow != first)
	swap(*follow,*first);
	return follow;	
}
template <typename Iterator>
void _quick_sort(Iterator first,Iterator last){
	if (first < last){
		Iterator mid = __partition(first,last);
		_quick_sort(first,mid);
		_quick_sort(mid+1,last);
	}
}
